// https://www.lintcode.com/problem/word-search/

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    public boolean exist(char[][] board, String word) {
        // write your code here
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (_exist(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    protected boolean _exist(char[][] board, String word, int row, int col, int idx) {
        if (idx == word.length()) {
            return true;
        }
        if ((row < 0) || (col < 0) || (row >= board.length) || (col >= board[0].length)) {
            return false;
        }
        Character ch = word.charAt(idx);
        if (board[row][col] == ch) {
            board[row][col] = '*';
            boolean r = _exist(board, word, row + 1, col, idx + 1) ||
                        _exist(board, word, row - 1, col, idx + 1) ||
                        _exist(board, word, row, col + 1, idx + 1) ||
                        _exist(board, word, row, col - 1, idx + 1);
            if (r) {
                return r;
            } else {
                board[row][col] = ch;
            }
        }
        return false;
    }
}